Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
- Option : A
- Explanation : Probability for the first record not colliding is x/x.
Probability for the second record not colliding is x-1/x.
(This is because one place is already occupied, So, favorable number of cases is x-1).
Probability for the third record not colliding is x-2/x.
Probability for the (m-1)th record not colliding is
.
Now the next (mth) record is resulting in a collision. Out of the x places, it should has to one of the (m-1) places already, filled. So,
You must be logged in to post a comment.
2. Which decision procedure has at least doubly exponential time complexity?
- Option : C
- Explanation :
You must be logged in to post a comment.
You must be logged in to post a comment.
- Option : B
- Explanation : Recursively applying the relation, we finally get T(n + 1) = c(n - 1) + T(1) = c(n - 1) + d hence order is n.
You must be logged in to post a comment.
You must be logged in to post a comment.
- Option : D
- Explanation :
You must be logged in to post a comment.
You must be logged in to post a comment.
5. F(x) = (7x6 + 3x4 + 17x + 9)/(0.01x3 * x-1) is Big - O of WHAT?
- Option : C
- Explanation :
You must be logged in to post a comment.
You must be logged in to post a comment.
You must be logged in to post a comment.